package jianzhioffer;

import java.util.HashMap;

// 剑指 Offer 57. 和为s的两个数字
public class TwoSum {


    // 1、哈希表
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(target - nums[i])) {
                map.put(nums[i], i);
            } else {
                return new int[]{nums[i], target - nums[i]};
            }
        }
        return new int[]{};
    }


    // 2、双指针
    public int[] twoSum2(int[] nums, int target) {
        int p = 0;
        int q = nums.length - 1;
        while (p < q) {
            // 让q指针先滑动一会儿
            while (p < q && nums[q] > target) {
                q--;
            }
            if (nums[p] + nums[q] < target) {
                p++;
            } else if (nums[p] + nums[q] > target) {
                q--;
            } else {
                return new int[]{nums[p], nums[q]};
            }
        }
        return new int[]{};
    }
}
